// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。
// 返回 s 所有可能的分割方案。

// 回文串 是正着读和反着读都一样的字符串。

const partition = function (s: string): string[][] {
    const res: string[][] = []; // 结果数组
    const path: string[] = []; // 当前路径
    partition_DFS(s, res, path, 0);
    return res;
};

function partition_DFS(s: string, res: string[][], path: string[], startIndex: number): void {
    // 递归出口，如果没有字符可以切割
    if (startIndex === s.length) {
        res.push(Array.from(path));// 这里需要用到拷贝
        return;
    }
    // 否则遍历剩余字符串，并继续分串
    for (let i = startIndex; i < s.length; i++) {
        // 如果不满足回文串，则直接跳过当前轮次，相当于剪枝
        if (!partition_check(s, startIndex, i)) {
            continue;
        } else {
            path.push(s.slice(startIndex, i + 1)); // 将当前回文串加入结果数组
            partition_DFS(s, res, path, i + 1); // 重置起点i
            path.pop(); // 回溯过程
        }
    }
}
// 检查是否是回文串
function partition_check(checkStr: string, left: number, right: number): boolean {
    while (left < right) {
        if (checkStr[left] !== checkStr[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

partition("aab")


// 这道题目是一道很好的考察回溯算法的题型
// 首先这里使用DFS，DFS的过程是声明一个字符起点
// 然后逐个遍历后续字符，当字符满足回文串的时候，就把它加入当前路径
// 这个过程是严格的以起点开始从左往右进行的，如果发现不满足回文串
// 那么直接跳过当前轮次，扩大子串来判断是否是回文串，如aba中的ab不是回文串，那么就往右扩大到aba
// 然后每进入递归，实际上进行的分串操作，在每一轮把子回文串加入当前路径，都不能忘记回溯路径
// 而当扫描到原字符串边界时，就可以判断当前路径合理，将当前路径拷贝到结果数组中
// 值得反复练习，结合纸上对于这道题目画出DFS路径非常重要！